#include <stdio.h>
#include <stdlib.h>
#include "binary_tree.h"

/*创建空树*/
BSTREE *bstree_create(void)
{
	BSTREE *bstree = malloc(sizeof(BSTREE));
	bstree->root = NULL;
	bstree->size = 0;
	return bstree;
}
//递归
void clear(BSTREE_NODE **root){
	if(*root){
		//清空左子树
		clear(&(*root) -> left);
		//清空右子树
		clear(&(*root) -> right);
		//释放root
		free(*root);
		*root = NULL;
		}
	}
void bstree_clear(BSTREE *bstree){
	clear(&(bstree -> root));
	bstree -> size = 0;
	}
/*销毁树*/
void bstree_destroy(BSTREE *bstree){
	//使其成为空树
	bstree_clear(bstree);
	free(bstree);
}
/*创建节点*/
BSTREE_NODE *node_create(int data)
{
	BSTREE_NODE *node =malloc(sizeof(BSTREE_NODE));
	node->data = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}
void insert(BSTREE_NODE *node, BSTREE_NODE **root)
{
	if(*root == NULL)
	{
		*root = node;
	}
	else
	{
		/*（子）树的根节点比较*/
		if(node->data < (*root)->data)
		{	
			insert(node, &((*root)->left));
		}
		else
		{
			insert(node, &((*root)->right));
		}
	}	
}
/*插入节点*/
void bstree_insert(BSTREE *bstree, int data)
{
	insert(node_create(data), &bstree->root);
	(bstree->size)++;
}

void print(BSTREE_NODE *root, int level)
{
	int i = 0;
	if(root)
	{
		print(root->right, level+1);
		for(i=0; i<level; i++)
		{
			printf("  ");
		}
		printf("%d\n", root->data);
		print(root->left, level+1);
	}
}
/*按树型打印相应的节点*/
void bstree_print(BSTREE *bstree)
{
	print(bstree->root, 0);
}
//中序遍历
void bstree_midtravel(BSTREE *bstree){
	midtravel (bstree -> root);
	printf("\n");
	}

void midtravel(BSTREE_NODE *root){
	if(root){
		midtravel(root -> left);
		printf("%d ",root -> data);
		midtravel(root -> right);
		}
	}
void pertravel(BSTREE_NODE *root){
	if(root){
		printf("%d ",root -> data);
		pertravel(root -> left);
		pertravel(root -> right);
		}
	}
void bstree_pertravel(BSTREE *bstree){
		pertravel(bstree -> root);
		printf("\n");
	}
void postravel(BSTREE_NODE *root){
	if(root){
		postravel(root -> left);
		postravel(root -> right);
		printf("%d ",root -> data);
		}
	}
void bstree_postravel(BSTREE *bstree){
		postravel(bstree -> root);
		printf("\n");
	}
